package com.zhouyong.leetcode.反转链表206;

import com.zhouyong.leetcode.ListNode;

/**
 * @Author 99
 * @Date 2022/9/25 11:26
 * @Version 1.0
 */
public class Test {

    public static void main(String[] args) {
        ListNode node = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4, new ListNode(5)))));
        System.out.println(reverseList(node));
    }

    // 给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
    // 输入：head = [1,2,3,4,5]
    // 输出：[5,4,3,2,1]
    public static ListNode reverseList(ListNode head) {

        // 用到了迭代的方式
        // 时间复杂度：o(N)
        // 空间复杂度：o(1)
//        ListNode prev = null;
//        ListNode curr = head;
//        while (curr != null) {
//            ListNode next = curr.next;
//            curr.next = prev;
//            prev = curr;
//            curr = next;
//        }
//        return prev;

        // 暴力解法
        // 时间复杂度：o(N)
        // 空间复杂度：o(N)
//        ListNode ans = null;
//        for (ListNode x = head; x != null; x = x.next) {
//            ans = new ListNode(x.val, ans);
//        }

        // 递归的方式1
        // return reverseListAgain(head, null);

        // 递归的方式2
        if (head == null || head.next == null) {
            return head;
        }
        ListNode newHead = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return newHead;
    }

    public static ListNode reverseListAgain(ListNode node, ListNode newNode) {
        if (node == null) {
            return newNode;
        } else {
            newNode = new ListNode(node.val, newNode);
        }
        return reverseListAgain(node.next, newNode);
    }
}
